Exercise: Heaps - Data Structures with Generic Types in Python

Task#

Implement the remove(i) method, that removes the value stored in a[i] in a BinaryHeap. This method should run in $O(\log n)$ time.

Sample input

The sample input will be as follows:

[0, 1, 2, 3, 4, 5, 6]

Expected output

The expected output will be as follows:

Original Heap:
[0, 1, 2, 3, 4, 5, 6]
Heap after removal from index 2:
[0, 1, 5, 3, 4, 6]

main.py

base.py

utils.py

from utils import new_array
from base import BaseSet
import random
# Left root
def left(i):
    return 2*i + 1
# Right root
def right(i):
    return 2*(i+1)
# Parent root
def parent(i):
    return (i-1)//2
# Main class
class BinaryHeap(BaseSet):
    def __init__(self, iterable=[], a=None):
        if a: 
            self._make_heap(a)
        else:
            self._initialize()
            self.add_all(iterable)
    # Function to create heap
    def _make_heap(self, a):
        self.a = a
        self.n = len(a)
        for i in range(self.n//2-1, -1, -1):
            self.trickle_down(i)
    # Initialize function        
    def _initialize(self):
        self.a = new_array(1)
        self.n = 0

Enter to Rename, Shift+Enter to Preview

Task to implement remove() in BinaryHeap